package heap

// 将一个切片堆化
// 思路：
// 首先考虑将任意一个位置i的元素，将该元素的所有子节点堆化该如何做呢？
// 1. 先将该元素的左子节点和右子节点进行堆化
// 2. 然后判断该元素和它的左右子节点的大小关系，
// 如果该元素比它的左右子节点都大，则不需要交换
// 如果该元素比它的左子节点小，则交换该元素和它的左子节点
// 如果该元素比它的右子节点小，则交换该元素和它的右子节点
// 3. 交换后，继续对该元素的子节点进行堆化
// 4. 直到该元素的左右子节点都比它小，或者该元素没有子节点为止
// 5. 注意：如果该元素没有子节点，则不需要堆化
// 6. 注意：如果该元素只有一个子节点，则只需要堆化该子节点即可
// 7. 注意：如果该元素是最后一个元素，则不需要堆化
// 8. 注意：如果该元素是根节点，则需要堆化整个切片
// 疑问，如果父元素和左右子元素已经堆化了，开始执行左子元素与孙子元素的堆化的时候，假如堆化结果又修改了左子元素，那岂不是得重新堆化父元素吗？
// 9. 答案是不会的，因为我们在堆化的时候，都是从下往上堆化的，这就能保证已经堆化的部分的顶必然是该部分的最大值或最小值，只需要用这个最值参与向上的比较即可了，不会产生回溯。
//    但确实可能会发生向下的递归，因为当前堆化的部分的最大值可能会比父元素大，于是和父元素的位置交换，这时候已堆化的部分可能就不符合堆要求了，所以我们需要向下递归。

// 堆的数组表示
// 1. 堆的数组表示是一个完全二叉树，
// 2. 堆的数组表示是一个一维数组，
// 3. 堆的数组表示是一个从0开始的数组，第i个元素的左子节点是2*i+1，右子节点是2*i+2，父节点是(i-1)/2。比如第0个元素的左子节点是1，右子节点是2，父节点是-1；第1个元素的左子节点是3，右子节点是4，父节点是0；第2个元素的左子节点是5，右子节点是6，父节点是0；第3个元素的左子节点是7，右子节点是8，父节点是1；第4个元素的左子节点是9，右子节点是10，父节点是1；第5个元素的左子节点是11，右子节点是12，父节点是2；第6个元素的左子节点是13，右子节点是14，父节点是2。
// 4. 基于元素的下标和左右子节点以及父节点的下标关系，我们可以很方便的实现堆的插入和删除操作。
// 5. 堆的插入操作是将新元素插入到数组的末尾，然后向上调整堆的结构，
// 6. 堆的删除操作是将堆顶元素删除，然后将最后一个元素放到堆顶，然后向下调整堆的结构。
// 7. 堆的插入和删除操作的时间复杂度都是O(log n)，

// 基于某个索引i的元素进行堆化
func heapify(arr []int, i int) {
	// 1. 先将该元素的左子节点和右子节点进行堆化
	// 必须要先堆化子节点，因为子节点可能会比父节点大
	// 如果子节点比父节点大，则需要交换父节点和子节点的位置
	// 如果子节点比父节点小，则不需要交换
	// 如果子节点不存在，则不需要堆化
	left := 2*i + 1
	right := 2*i + 2
	if left < len(arr) { // 左子节点存在
		heapify(arr, left)
	}
	if right < len(arr) { // 右子节点存在
		heapify(arr, right)
	}
	// 2. 然后判断该元素和它的左右子节点的大小关系，
	if left < len(arr) && arr[i] < arr[left] {
		arr[i], arr[left] = arr[left], arr[i]
	}
	if right < len(arr) && arr[i] < arr[right] {
		arr[i], arr[right] = arr[right], arr[i]
	}
}

// 堆化整个数组
func heapifyAll(arr []int) {
	// 1. 从最后一个非叶子节点开始，向前遍历
	// 2. 对每个非叶子节点进行堆化
	// 3. 堆化的顺序是从下往上，从右往左
	// 4. 堆化的时间复杂度是O(n)
	// 注意：
	// 为什么从 len(arr)/2 - 1 开始，因为从 len(arr)/2 开始的元素都是叶子节点，不需要堆化
	// 如果从len(arr)-1开始，则会导致最后一个元素的左子节点和右子节点都不存在，就算执行了heapify也不会有任何效果
	for i := len(arr)/2 - 1; i >= 0; i-- {
		heapify(arr, i)
	}
}

// 堆排序
// 思路：
// 1. 首先对数组进行堆化，构建最大堆
// 2. 然后将堆顶元素（最大值）与最后一个元素交换
// 3. 交换后，最后一个元素是当前未排序部分的最大值，将其从未排序部分移除
// 4. 然后对堆顶元素进行堆化
// 5. 重复步骤2-4，直到所有元素都被排序
// 6. 堆排序的时间复杂度是O(n log n)
// 7. 堆排序的空间复杂度是O(1)
// 8. 堆排序是不稳定的排序算法，因为相同的元素可能会交换位置
func HeapSort(arr []int) {
	// 1. 首先对数组进行堆化，构建最大堆
	heapifyAll(arr)
	// 2. 然后将堆顶元素（最大值）与最后一个元素交换
	for i := len(arr) - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		// 3. 交换后，最后一个元素是当前未排序部分的最大值，将其从未排序部分移除
		// 4. 然后对堆顶元素进行堆化
		heapify(arr[:i], 0)
	}
}
